How does FEDEX or UPS choose the optimal route to deliver packages? by Anil Kumar Gowda Thammaiah, Sunil Golla
A Short Answer Transportation of goods is an important task in today’s society. People need to send packages, documents or other important things from one place to another on a regular basis. We usually rely on courier services to do this job for us. Most customers wish to receive their packages within one to two days, which makes the courier service industry an essential tool for any business. Therefore, the company’s goal is to make sure their customer’s delivery requests succeed their expectations. In order to accomplish this, huge amounts of money is being spent by the courier service daily on fuel, equipment, maintenance of equipment and wages. Time is money, and using the most efficient route to deliver packages can drastically reduce the time it takes to make these deliveries. Even small improvements can lead to huge improvements in absolute terms. The improvements are not only in terms of better mileage, they also help cut fuel usage, decrease carbon emissions, improve asset utilization, and increase customer service. A few notable players in the USA for providing courier services are United Parcel Service, Inc. (UPS), DHL Express, FedEx Corporation, Etc. Let’s assume an average driver makes about 120 deliveries per day. To figure out how many different possible routes that driver could travel, just start multiplying: 120! = 120 \times119\times118.........\times3\times2\times1 = 6.68\times10^{198} This result far exceeds the age of the Earth in nanoseconds. So, how to find the most optimal route among 6.68\times10^{198} combinations that could minimize the total expense by meeting the demands of the customers? This question can be divided into three sub-questions. 1.There might be several delivery centers in a city, so which delivery center is responsible for a particular package? This solution to this question is relatively very simple. Each delivery center can be made responsible for a particular set of zip codes and the package belonging to a particular zip code can be routed to its corresponding delivery center. 2.Now the packages arrived at the delivery center, there might be huge number of packages that several trucks might be required to deliver these packages. So, how to split the routes most effectively between these trucks if more than one truck is being used? The coverage area of the delivery center and number of packages and trucks available for delivery are the two factors that need to be considered to answer this question. A single truck might not be sufficient always to make the deliveries. If two packages need to be delivered to a particular apartment, it is better to have those two packages on the same truck instead of two different trucks. This could be termed as “The Vehicle Routing Problem” and an optimal solution to this problem would result in providing the improvements discussed earlier. 3.Once the packages are in the truck and if there are a set of addresses where the packages are to be delivered, what is an efficient order to visit them? The truck needs to go through the addresses that have been given and there are different routes that can be taken. If the driver visits a building and delivers a package, then goes around and comes back to the same building but this time for a different package, then this is not an efficient route. This can be termed as “The Traveling Salesman Problem”. A Long Answer The Vehicle Routing Problem The vehicle routing problem (VRP) is a well known combinatorial optimization and integer programming problem. Traditionally, the VRP is defined as a routing problem with a single depot, a set of customers, multiple vehicles and the objective to minimize the total cost while servicing every customer. Each vehicle that services customers starts the travel from the depot and finishes it in the depot as well. The objective of the typical VRP is to find the solution, at first, minimizing the total vehicle number required, and secondly, minimizing the length of the total traveled path. This problem was first formulated by Dantzig and Ramser (1959). The vehicle routing problem typically is described as a graph G=\left(V,E\right) and a set of homogeneous vehicles K=\left\{k_{1},k_{2},k_{3}......,k_{n}\right\} where t is the number of vehicles. The graph G consists of the nodes V=\left\{0,1,2,......,k\right\} where 0 is a depot and V\\{0} are k customers that need to be serviced, and edges E={x_{ij}} between each node where i\neq{j}, 0\leq{i}\leq{k} and 0\leq{j}\leq{k} For the set E, the cost matrix C is defined, where c_{ij} is the cost of the edge x_{ij}=\left(i,j\right), and c_{ii}=0 . Usually the VRP is treated as symmetric, where c_{ij}=c_{ji} . In the real world problem, the cost matrix is asymmetric and needs to be calculated from geographic data by using the shortest path algorithms. Moreover, if a vehicle set is not homogeneous, some roads can be forbidden for certain vehicles and allowed for others. The different shortest path can exist for a different vehicle type, so a different matrix needs to be calculated for all the different vehicle types. Various constraints can be added to the VRP. The defined constraints usually refer to real life situations. The most known constraint for the VRP is the capacity constraint. The capacity constraints S_{c}\sqsubseteq{S} are carriage limitations applied to each vehicle. A capacitated vehicle routing problem (CVRP) is usually defined with equal capacities for all vehicles. However, in real life vehicle fleet with different capacities can be used to solve the delivery problem. VRP Formulation The objective of VRP is min\sum_{i\epsilon{V}}\sum_{j\epsilon{V}}c_{ij}x_{ij} subject to constraints \sum_{i\epsilon{V}}x_{ij}=1 \forall{j\epsilon{V}}\backslash\left\{0\right\} \sum_{j\epsilon{V}}x_{ij}=1 \forall{i\epsilon{V}}\backslash\left\{0\right\} \sum_{i\epsilon{V}}x_{i0}=K \sum_{j\epsilon{V}}x_{0j}=K \sum_{i\notin{S}}\sum_{j\epsilon{S}}x_{ij}\geq{S_{c}} x_{ij}\epsilon{\left\{0,1\right\}} \forall{i,j}\epsilon{V} Savings algorithm Suppose that initially the solution to the VRP consists of using n vehicles and dispatching one vehicle to each one of the n demand points. The total tour length of this solution is, obviously, The algorithm can be described as follows. STEP 1: Calculate the savings s(i, j) = d(D, i) + d(D, j) d(i, j) for every pair (i, j) of demand points. STEP 2: Rank the savings s(i, j) and list them in descending order of magnitude. This creates the "savings list." Process the savings list beginning with the topmost entry in the list (the largest s(i, j)). STEP 3: For the savings s(i, j) under consideration, include link (i, j) in a route if no route constraints will be violated through the inclusion of (i, j) in a route, and if: a. Either, neither i nor j have already been assigned to a route, in which case a new route is initiated including both i and j. b. Or, exactly one of the two points (i or j) has already been included in an existing route and that point is not interior to that route (a point is interior to a route if it is not adjacent to the depot D in the order of traversal of points), in which case the link (i, j) is added to that same route. c. Or, both i and j have already been included in two different existing routes and neither point is interior to its route, in which case the two routes are merged. STEP 4: If the savings list s(i, j) has not been exhausted, return to Step 3, processing the next entry in the list; otherwise, stop: the solution to the VRP consists of the routes created during Step 3. (Any points that have not been assigned to a route during Step 3 must each be served by a vehicle route that begins at the depot D visits the unassigned point and returns to D.)Denoting the transportation cost between two given points i and j by c ij , the total transportation cost Da in is: Da= C0i + Ci0 + C0j + Cj0 Equivalently, the transportation cost D in figure is: Db= C0i + Cij + Cjo By combining the two routes one obtains the savings Sij : Sij = Da − Db = Ci0 + C0j −Cij Relatively large values of S ij indicate that it is attractive, with regard to costs, to visit points i and j on the same route such that point j is visited immediately after point. Example – VRP Consider a VRP where the Depot is node 0 and the nine points are the set of nodes that need to be serviced. The distances and savings between each node is provided in the below matrix.Since the distances are symmetric, the savings Sij is computed using the equation Sij = Da − Db = Ci0 + C0j −Cij and shown in the same matrix. The distances are below the diagonal and the savings are shown above the diagonal. For instance S 35= X 03+X 05 -X 35= 57+61-71=47 Distance (below diagonal) and Savings (above diagonal) matrix We assume that the capacity of each vehicle is 23 and apply the third step of the Savings algorithm to the savings list, as shown in Table 6-6. No constraint other than the maximum capacity one is assumed to exist. The processing of the savings list now proceeds as follows. The largest savings is associated with link (5, 9), so a tour consisting of {0, 5, 9, 0} is created. The second entry in the list is associated with link (8, 9). The initial route is therefore expanded to {0, 5, 9, 8, 0} since the conditions under Step 3 are satisfied by such an expansion. Next is the entry for link (7, 8) and expansion of the route to {0, 5, 9, 8, 7, 0} also turns out to be acceptable. However, expansion to {0, 4, 5, 9, 8, 7, 0}, as suggested by the next entry for link (4, 5), is impossible since such a route would imply a load of 24 units (> 23). Thus, link (4, 5) is rejected. So is link (7, 9)--both 7 and 9 are already in the tour; and (6, 9)--since 9 is interior to the tour. The appearance of link (3, 4) as the next entry in the savings list leads to formation of another tour {0, 3, 4, 0}. Next, the inclusion of point 6 in the first tour is acceptable and that tour is expanded to {0, 6, 5, 9, 8, 7, 0} with a load of 23 (meaning that this tour cannot be expanded further). Proceeding in the same way, points 2 and then 1 are successively added to the second tour, ending up with the tour {0, 1, 2, 3, 4, 0}, with a load of 19 units. Since all points have been included in a tour, that also means the completion of our procedure. The two tours are shown in Figure 6.31 and their combined length (total distance traveled) is 397 units. Travelling salesman problem TSP is one of the most intensively used method used by postal services all round the world. Basically in this problem a salesman need to visits each city one time and returns back to the city from the start point of traveling.The Traveling Salesman Problem is simple and its a combinatorial problem. In a traveling Salesman Problem a salesman needs to visit all “n” cities (“nodes”) in a cyclically order. A salesman in his tour needs to visit all cities each time and finish up when he reached the starting node or city. Travelling sales man Formulation TSP can be formulated as an integer linear program. Xij= {1 if the path goes from node i to node j and 0 other wise } For i=0,1,2,3......n .Let Cij be the distance from node i to node j. Then TSP can be written as the following integer linear programming problem: Although optimal algorithms exist for solving the TSP, like the IP formulation, industrial engineers have realized that it is computationally infeasible to obtain the optimal solution to TSP. And it has been proved that for large-size TSP, it is almost impossible to generate an optimal solution within a reasonable amount of time. Heuristics, instead of optimal algorithms, are extensively used to solved such problems. People conceived many heuristic algorithms to get near optimal solutions. Among them, there are greedy, 2-opt, 3-opt, simulated annealing, genetic algorithms, neural network approach, etc. But their efficiencies vary from case to case, from size to size. One such heuristic with a greedy approach is Nearest Neighbor Algorithm. Nearest Neighbour Algorithm The nearest neighbor algorithm was one of the first algorithms used to determine a solution to the TSP. It is a greedy algorithm for finding a sub-optimal solution to the TSP. The algorithm can be described as follows: Step 1: Start at the depot Step 2: Next address will be the closest as-yet-unvisited one (if there are two or more at the same closest distance, just pick any one of them) Step 3: Go there Step 4: Repeat 2 and 3 until no more unvisited nodes Step 5: End at the depot Example for TSP Consider a fully connected graph G where the depot is at node A and B, C, D and E are the set of nodes that need to be visited exactly once. The Nearest neighbor algorithm can be used to find the sub-optimal route as described below. A graph with 5 nodes where node A is the depot and B, C, D and E are the set of nodes that need to be visited exactly once. The route must start at node A as it is the depot. Among the nodes B, C D and E the nearest node is D with a cost of 185. The node D is marked as visited. Among the remaining unvisited nodes E, C and B the nearest unvisited node from D is E. Node E is marked as visited and the next node that need to be visited is C with a cost 165. The node B will be visited next as it is the only unvisited node remaining and the final route will be ADECBA. The total cost of the route would be: AD+DE+EC+CB+BA= 185+302+165+305+500=1457